grammar = {
    'Program': [['ProgramHead', 'DeclarePart', 'ProgramBody']],
    'ProgramHead': [['PROGRAM', 'ProgramName']],
    'ProgramName': [['ID']],
    'DeclarePart': [['TypeDecpart', 'VarDecpart', 'ProcDecpart']],
    'TypeDecpart': [['𝝴'], ['TypeDec']],
    'TypeDec': [['TYPE', 'TypeDecList']],
    'TypeDecList': [['Typeld', '=', 'TypeDef', ';', 'TypeDecMore']],
    'TypeDecMore': [['𝝴'], ['TypeDecList']],
    'Typeld': [['ID']],
    'TypeDef': [['BaseType'], ['StructureType'], ['ID']],
    'BaseType': [['INTEGER'], ['CHAR']],
    'StructureType': [['Array', 'Type'], ['Rec', 'Type']],
    'Array': [['ARRAY', '[', 'Low', '..', 'Top', ']', 'OF', 'BaseType']],
    'Low': [['INTC']],
    'Top': [['INTC']],
    'Rec': [['RECORD', 'FieldDecList', 'END']],
    'FieldDecList': [['BaseType', 'IdList', ';', 'FieldDecMore'], ['Array', 'Type', 'IdList', ';', 'FieldDecMore']],
    'FieldDecMore': [['𝝴'], ['FieldDecList']],
    'IdList': [['ID', 'IdMore']],
    'IdMore': [['𝝴'], [',', 'IdList']],
    'VarDecpart': [['𝝴'], ['VarDec']],
    'VarDec': [['VAR', 'VarDecList']],
    'VarDecList': [['TypeDef', 'VarIdList', ';', 'VarDecMore']],
    'VarDecMore': [['𝝴'], ['VarDecList']],
    'VarIdList': [['ID', 'VarldMore']],
    'VarldMore': [['𝝴'], [',', 'VarldList']],
    'ProcDecpart': [['𝝴'], ['ProcDec']],
    'ProcDec': [['PROCEDURE', 'ProcName', '(', 'ParamList', ')', ';', 'ProcDecPart', 'ProcBody', 'ProcDecMore']],
    'ProcDecMore': [['𝝴']],
    'ProcName': [['ID']],
    'ParamList': [['𝝴'], ['ParamDecList']],
    'ParamDecList': [['Param', 'ParamMore']],
    'ParamMore': [['𝝴'], [';', 'ParamDecList']],
    'Param': [['TypeDef', 'FormList'], ['VAR', 'TypeDef', 'FormList']],
    'FormList': [['ID', 'FidMore']],
    'FidMore': [['𝝴'], [',', 'FormList']],
    'ProcDecPart': [['DeclarePart']],
    'ProcBody': [['ProgramBody']],
    'ProgramBody': [['BEGIN', 'StmList', 'END']],
    'StmList': [['Stm', 'StmMore']],
    'StmMore': [['𝝴'], [';', 'StmList']],
    'Stm': [['ConditionalStm'], ['LoopStm'], ['InputStm'], ['OutputStm'], ['ReturnStm'], ['ID', 'AssCall']],
    'AssCall': [['AssignmentRest'], ['CallStmRest']],
    'AssignmentRest': [['VariMore', ':=', 'Exp']],
    'ConditionalStm': [['IF', 'RelExp', 'THEN', 'StmList', 'ELSE', 'StmList', 'FI']],
    'LoopStm': [['WHILE', 'RelExp', 'DO', 'StmList', 'ENDWH']],
    'InputStm': [['READ', '(', 'Invar', ')']],
    'Invar': [['ID']],
    'OutputStm': [['WRITE', '(', 'Exp', ')']],
    'ReturnStm': [['RETURN']],
    'CallStmRest': [['(', 'ActParamList', ')']],
    'ActParamList': [['𝝴'], ['Exp', 'ActParamMore']],
    'ActParamMore': [['𝝴'], [',', 'ActParamList']],
    'RelExp': [['Exp', 'OtherRelE']],
    'OtherRelE': [['CmpOp', 'Exp']],
    'Exp': [['Term', 'OtherTerm']],
    'OtherTerm': [['𝝴'], ['AddOp', 'Exp']],
    'Term': [['Factor', 'OtherFactor']],
    'OtherFactor': [['𝝴'], ['MultOp', 'Term']],
    'Factor': [['(', 'Exp', ')'], ['INTC'], ['Variable']],
    'Variable': [['ID', 'VariMore']],
    'VariMore': [['𝝴'], ['[', 'Exp', ']'], ['.', 'FieldVar']],
    'FieldVar': [['ID', 'FieldVarMore']],
    'FieldVarMore': [['𝝴'], ['[', 'Exp', ']']],
    'CmpOp': [['<'], ['=']],
    'AddOp': [['+'], ['-']],
    'MultOp': [['*'], ['/']],
}

predict_sets = {
    ('ID', 'VarldMore'): {';', ','},
    (',', 'VarldList'): {'ID'},
    ('ProcDec',): {'PROCEDURE'},
    ('ID', 'IdMore'): {'=', '<', ';', ',', '+', '-', '*', '/', 'THEN', 'ELSE', 'FI', 'DO', 'ENDWH', ')', 'END'},
    ('ProgramHead', 'DeclarePart', 'ProgramBody'): {'PROGRAM'},
    ('PROGRAM', 'ProgramName'): {'PROGRAM'},
    ('ID',): {'ID'},
    ('TypeDecpart', 'VarDecpart', 'ProcDecpart'): {'TYPE', 'VAR', 'PROCEDURE', 'BEGIN'},
    ('𝝴',): {'VAR', 'PROCEDURE', 'BEGIN'},
    ('TypeDec',): {'TYPE'},
    ('TYPE', 'TypeDecList'): {'TYPE'},
    ('Typeld', '=', 'TypeDef', ';', 'TypeDecMore'): {'ID'},
    ('𝝴',): {'VAR', 'PROCEDURE', 'BEGIN'},
    ('TypeDecList',): {'ID'},
    ('ID',): {'ID'},
    ('BaseType',): {'INTEGER', 'CHAR'},
    ('StructureType',): {'ARRAY', 'RECORD'},
    ('ID',): {'ID'},
    ('INTEGER',): {'INTEGER'},
    ('CHAR',): {'CHAR'},
    ('Array', 'Type'): {'ARRAY'},
    ('Rec', 'Type'): {'RECORD'},
    ('ARRAY', '[', 'Low', '..', 'Top', ']', 'OF', 'BaseType'): {'ARRAY'},
    ('INTC',): {'INTC'},
    ('INTC',): {'INTC'},
    ('RECORD', 'FieldDecList', 'END'): {'RECORD'},
    ('BaseType', 'IdList', ';', 'FieldDecMore'): {'INTEGER', 'CHAR'},
    ('Array', 'Type', 'IdList', ';', 'FieldDecMore'): {'ARRAY'},
    ('𝝴',): {'END'},
    ('FieldDecList',): {'INTEGER', 'CHAR', 'ARRAY'},
    (';',): {';'},
    (',', 'IdList'): {','},
    ('VarDecpart',): {'PROCEDURE', 'BEGIN'},
    ('VarDec',): {'VAR'},
    ('VAR', 'VarDecList'): {'VAR'},
    ('TypeDef', 'VarIdList', ';', 'VarDecMore'): {'INTEGER', 'CHAR', 'ARRAY', 'RECORD', 'ID'},
    ('𝝴',): {'PROCEDURE', 'BEGIN'},
    ('VarDecList',): {'INTEGER', 'CHAR', 'ARRAY', 'RECORD', 'ID'},
    ('ID', 'VarIdMore'): {'ID'},
    (';',): {';'},
    (',', 'VarIdList'): {','},
    ('BEGIN',): {'BEGIN'},
    ('PROCEDURE',): {'PROCEDURE'},
    ('PROCEDURE', 'ProcName', '(', 'ParamList', ')', ';', 'ProcDecPart', 'ProcBody', 'ProcDecMore'): {'PROCEDURE'},
    ('𝝴',): {'BEGIN'},
    ('PROCEDURE',): {'PROCEDURE'},
    ('ID',): {'ID'},
    ('𝝴',): {')'},
    ('ParamDecList',): {'INTEGER', 'CHAR', 'ARRAY', 'RECORD', 'ID', 'VAR'},
    ('Param', 'ParamMore'): {'INTEGER', 'CHAR', 'ARRAY', 'RECORD', 'ID', 'VAR'},
    ('𝝴',): {'('},
    (';', 'ParamDecList'): {';'},
    ('TypeDef', 'FormList'): {'INTEGER', 'CHAR', 'ARRAY', 'RECORD'},
    ('VAR', 'TypeDef', 'FormList'): {'VAR'},
    ('ID', 'FidMore'): {'ID'},
    ('𝝴',): {';', ')'},
    (',', 'FormList'): {','},
    ('TypeDecpart', 'VarDecpart', 'ProcDecpart'): {'TYPE', 'VAR', 'PROCEDURE', 'BEGIN'},
    ('BEGIN',): {'BEGIN'},
    ('BEGIN', 'StmList', 'END'): {'BEGIN'},
    ('Stm', 'StmMore'): {'ID', 'IF', 'WHILE', 'RETURN', 'READ', 'WRITE'},
    ('𝝴',): {'ELSE', 'FI', 'END', 'ENDWH'},
    (';', 'StmList'): {';'},
    ('IF',): {'IF'},
    ('WHILE',): {'WHILE'},
    ('READ',): {'READ'},
    ('WRITE',): {'WRITE'},
    ('RETURN',): {'RETURN'},
    ('ID',): {'ID'},
    (':=',): {':='},
    ('(',): {'('},
    ('[', 'Exp', ']'): {'[', 'DOT', ':='},
    ('IF', 'RelExp', 'THEN', 'StmList', 'ELSE', 'StmList', 'FI'): {'IF'},
    ('WHILE', 'RelExp', 'DO', 'StmList', 'ENDWH'): {'WHILE'},
    ('READ', '(', 'Invar', ')'): {'READ'},
    ('ID',): {'ID'},
    ('WRITE', '(', 'Exp', ')'): {'WRITE'},
    ('RETURN',): {'RETURN'},
    ('(', 'ActParamList', ')'): {'('},
    ('𝝴',): {')'},
    ('Exp', 'ActParamMore'): {'(', 'INTC', 'ID'},
    ('𝝴',): {'}', ','},
    (',', 'ActParamList'): {','},
    ('Exp', 'OtherRelE'): {'(', 'INTC', 'ID'},
    ('CmpOp', 'Exp'): {'<', '='},
    ('Exp', 'OtherTerm'): {'(', 'INTC', 'ID'},
    ('𝝴',): {'<', '=', ']', 'THEN', 'ELSE', 'FI', 'DO', 'ENDWH', ')', 'END', ';', ','},
    ('AddOp', 'Exp'): {'+', '-'},
    ('Term', 'OtherFactor'): {'(', 'INTC', 'ID'},
    ('𝝴',): {'THEN', 'ELSE', 'FI', 'DO', 'ENDWH', ')', 'END', ';', ','},
    ('MultOp', 'Term'): {'*', '/'},
    ('(', 'Exp', ')'): {'('},
    ('INTC',): {'INTC'},
    ('ID', 'VariMore'): {'ID'},
    ('𝝴',): {'=', 'THEN', 'ELSE', 'FI', 'DO', 'ENDWH', ')', 'END', ';', ','},
    ('[', 'Exp', ']'): {'['},
    ('.', 'FieldVar'): {'.'},
    ('ID', 'FieldVarMore'): {'ID'},
    ('𝝴',): {'=', 'THEN', 'ELSE', 'FI', 'DO', 'ENDWH', ')', 'END', ';', ','},
    ('[', 'Exp', ']'): {'['},
    ('<',): {'<'},
    ('=',): {'='},
    ('+',): {'+'},
    ('-',): {'-'},
    ('*',): {'*'},
    ('/',): {'/'}
}


class Node:
    def __init__(self, node_type, value=None):
        self.node_type = node_type
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)


def print_tree(node, indent=''):
    print(f"{indent}{node.node_type}", end='')
    if node.value is not None:
        print(f": {node.value}")
    else:
        print()

    for child in node.children:
        print_tree(child, indent + '  ')


def create_ll1_table(grammar, predict_sets):
    ll1_table = {}
    for non_terminal, productions in grammar.items():
        ll1_table[non_terminal] = {}
        for production in productions:
            if tuple(production) in predict_sets:
                for terminal in predict_sets[tuple(production)]:
                    ll1_table[non_terminal][terminal] = production
    return ll1_table


ll1_table = create_ll1_table(grammar, predict_sets)
print(ll1_table)


def parse(input_tokens, ll1_table):
    stack = [('$', None), ('program', None)]
    input_tokens.append(('$', None))

    current_token_index = 0
    current_token, current_value = input_tokens[current_token_index].value, input_tokens[current_token_index].token_type

    tree = Node('Program')

    while len(stack) > 0:
        top_of_stack, top_value = stack[-1]
        print(top_of_stack, top_value)
        print("current_token: " + current_token)

        if top_of_stack == current_token:
            stack.pop()
            current_node = Node(top_of_stack, current_value)
            tree.add_child(current_node)

            current_token_index += 1
            current_token, current_value = input_tokens[current_token_index].value, input_tokens[
                current_token_index].token_type
        elif top_of_stack not in ll1_table:  # 如果栈顶是终结符
            raise Exception(f"Error: {top_of_stack} 不是非终结符")
        else:
            rule = ll1_table[top_of_stack].get(current_token, None)
            if rule is None:
                raise Exception(f"Error: 找不到对应的规则 ({top_of_stack}, {current_token})")
            stack.pop()
            for symbol in reversed(rule):
                stack.append((symbol, None))

    if current_token != '$':
        raise Exception("Error: 输入流未结束,当前token: " + current_token)

    return tree

# 运行分析程序
# tree = parse(input_tokens, ll1_table)
# print_tree(tree)
